package com.sfx.算法专题.回溯.递归;

import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-09-09
 * Time: 11:17
 */
public class Code_1_hanota {
    static class Solution {
        // 将a柱子中的n个盘子,借助b柱子,移动到c柱子上
        private void dfs(List<Integer> a, List<Integer> b, List<Integer> c,int n) {
            if(n == 1) {
                c.add(a.remove(a.size()-1));
                return;
            }
            // 将a柱子中的n-1个盘子,从c移动到b中-用到上一个逻辑
            dfs(a,c,b,n-1);
            // 再把a盘子上的最后一个放到c盘子上
            c.add(a.remove(a.size()-1));
            // 将b柱子中的n-1个盘子,从a移动到c中-用到上一个逻辑
            dfs(b,a,c,n-1);
        }
        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            dfs(A,B,C,A.size());
        }
    }
}